package com.lsa.letcode.the143.reorderList;

import com.lsa.letcode.common.ListNode;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void reorderList(ListNode head) {
    	if (head == null){
    		return;
    	}
    	ListNode center = center(head);
    	ListNode half2Rev = reverse(center.next);
    	center.next = null;
    	merge(head, half2Rev);
    }

	private void merge(ListNode head1, ListNode head2) {
		while(head1 != null){
			ListNode next1 = head1.next;
			ListNode next2 = head2 != null? head2.next : null;
			
			head1.next = head2;
			if (head2 != null){
				head2.next = next1;
			}
			
			head1 = next1;
			head2 = next2;
		}
	}

	private ListNode reverse(ListNode head) {
		ListNode prev = null;
        while(head != null) {
        	ListNode next = head.next;
        	head.next = prev;
        	prev = head;
        	head = next;
        }
        
        return prev;
	}

	private ListNode center(ListNode head) {
		ListNode slow = head;
		ListNode fast = head.next;
		while(fast != null && fast.next != null){
			slow = slow.next;
			fast = fast.next;
			if (fast != null){
				fast = fast.next;
			}
		}
		return slow;
	}
}